#!/usr/bin/ruby
# -*- ruby -*-
#
# http://programmingpraxis.com/2013/05/17/coin-change-part-1/

require 'pp'
require 'set'

def count(change_left, increments, all_accumulated, memo = Set.new, accumulated = {})
  memo << accumulated

  if change_left == 0
    all_accumulated << accumulated
  elsif change_left > 0
    increments.each do |increment|
      _accumulated = accumulated.clone
      _accumulated[increment] ||= 0
      _accumulated[increment] += 1

      count(change_left - increment, increments, all_accumulated, memo, _accumulated) unless memo.include?(_accumulated)
    end
  end
end

acc = Set.new
count((ARGV.first || 40).to_i, [25, 10, 5, 1], acc)

puts acc.size
